import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public int usedSize;

    TestHeap() {
        this.elem = new int[10];
    }

    /**
     * 建大堆
     * @param array
     */
    public void creteHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }
        for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
            adjustDown(parent,this.usedSize);
        }
    }
    public void adjustDown(int root,int len) {
        int parent = root;
        int child = 2*parent+1;

        while (child < len) {
            //判断是否有右孩子
            if(child+1 < len && this.elem[child] < this.elem[child+1]) {
                child++;
            }
            //如果左右孩子的最大值大于父亲的值就交换
            if(this.elem[parent] < this.elem[child]) {
                int tmp = this.elem[parent];
                this.elem[parent] = this.elem[child];
                this.elem[child] = tmp;
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }
    public void adjustUp(int child) {
        int parent = (child-1)/2;
        while(parent >= 0) {
            if(this.elem[parent] < this.elem[child]) {
                int tmp = this.elem[parent];
                this.elem[parent] = this.elem[child];
                this.elem[child] = tmp;
                child = parent;
                parent = (child-1)/2;
            } else {
                break;
            }
        }
    }

    /**
     * 入队
     * @param val
     */
    public void push(int val) {
        //扩容
        if(this.isFull()) {
            this.elem = Arrays.copyOf(this.elem,this.elem.length*2);
        }
        this.elem[this.usedSize] = val;
        this.usedSize++;
        adjustUp(this.usedSize-1);
    }
    public boolean isFull() {
        return this.usedSize == this.elem.length;
    }

    /**
     * 出队首元素
     */
    public void pop() {
        if(this.isEmpty()) return;

        int tmp = this.elem[0];
        this.elem[0] = this.elem[this.usedSize-1];
        this.elem[this.usedSize-1] = tmp;
        this.usedSize--;
        this.adjustDown(0,this.usedSize);
    }
    public boolean isEmpty() {
        return this.usedSize == 0;
    }

    /**
     * 获取队头元素
     * @return
     */
    public int peek() {
        if(this.isEmpty()) {
            throw new RuntimeException("队列为空");
        }

        return this.elem[0];
    }

    /**
     * 堆排序
     * 先交换第一个和最后一个元素，再调整树
     * 从小到大排序
     */
    public void heapSort() {
        if(this.isEmpty()) return;

        int len = this.usedSize-1;
        while(len > 0) {
            int tmp = this.elem[len];
            this.elem[len] = this.elem[0];
            this.elem[0] = tmp;
            adjustDown(0,len);
            len--;
        }
    }
}
